package main.java.exercise;

import main.java.framework.StudentInformation;
import main.java.framework.StudentSolution;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class StudentSolutionImplementation implements StudentSolution {
    @Override
    public StudentInformation provideStudentInformation() {
        return new StudentInformation(
                "", // Vorname
                "", // Nachname
                "" // Matrikelnummer
        );
    }

    public void heapifyUp(PriorityQueue priorityQueue, int index) {
        if (index <= 1) return;

        int middle = index / 2;
        if (priorityQueue.getWeight(index) < priorityQueue.getWeight(middle)) {
            priorityQueue.swap(index, middle);
            heapifyUp(priorityQueue, middle);
        }
    }

    public void heapifyDown(PriorityQueue priorityQueue, int index) {
        int n = priorityQueue.length() - 1, left, right, twoI;

        if (2 * index > n) return;
        else if (2 * index < n) {
            left = 2 * index; right = left + 1;
            twoI = (priorityQueue.getWeight(right) < priorityQueue.getWeight(left)) ?
                right : left;
        } else{
            twoI = 2 * index;
        }

        if (priorityQueue.getWeight(twoI) < priorityQueue.getWeight(index)) {
            priorityQueue.swap(index, twoI);
            heapifyDown(priorityQueue, twoI);
        }
    }

    public double prim(Graph g, PriorityQueue q, int[] predecessors) {
        int v;
        double sum = 0d;
        double vwWeight, wPrev;

        ArrayList<Integer> selected = new ArrayList<>(g.numberOfVertices());

        for (int i = 1; i <= g.numberOfVertices(); i++) {
            q.add(Double.MAX_VALUE, i);
        }

        while (!q.isEmpty()) {
            v = q.removeFirst();

            if (!g.isRelevant(v)) continue;

            selected.add(v);

            for (int w : g.getNeighbors(v)) {
                if (selected.contains(w) || !g.isRelevant(w))
                    continue;

                vwWeight = g.getEdgeWeight(v, w);
                wPrev = g.getEdgeWeight(predecessors[w], w);
                if (wPrev < vwWeight && wPrev >= 0)
                    continue;

                predecessors[w] = v;
                q.decreaseWeight(vwWeight, w);
            }
        }

        for (Integer w : selected) {
            if (predecessors[w] == 0) continue;
            sum += g.getEdgeWeight(predecessors[w], w);
        }

        return sum;
    }

    public int findset(UnionFindDataStructure unionFindDataStructure, int vertexId) {
        int parent = vertexId;
        while ((vertexId = unionFindDataStructure.getParent(vertexId)) != parent)
            parent = vertexId;
        return parent;
    }

    public double kruskal(Graph g, UnionFindDataStructure u, boolean[] chosenEdges) {
        int chosenEdgesCount = 0;
        int[][] orderedEdges = g.getEdgesOrderedByWeight();

        assert orderedEdges.length == chosenEdges.length;

        int a, b, v, w, sum = 0;
        for (int i = 1; i <= g.numberOfVertices(); i++)
            u.makeset(i);

        for (int i = 0; i < orderedEdges.length; i++) {
            v = orderedEdges[i][0];
            w = orderedEdges[i][1];

            if (!g.isRelevant(v) || !g.isRelevant(w)) continue;

            a = findset(u, v);
            b = findset(u, w);

            if (a == b) continue;

            u.union(a, b);
            chosenEdges[i] = true;
            ++chosenEdgesCount;
            sum += g.getEdgeWeight(v, w);

            if (chosenEdgesCount == g.numberOfVertices() - 1)
                break;
        }

        return sum;
    }

}
